/**
 * //给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * //
 * // 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * //
 * //
 * //
 * //
 * // 必须在不使用库的sort函数的情况下解决这个问题。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [2,0,2,1,1,0]
 * //输出：[0,0,1,1,2,2]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [2,0,1]
 * //输出：[0,1,2]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // n == nums.length
 * // 1 <= n <= 300
 * // nums[i] 为 0、1 或 2
 * //
 * //
 * //
 * //
 * // 进阶：
 * //
 * //
 * // 你可以不使用代码库中的排序函数来解决这道题吗？
 * // 你能想出一个仅使用常数空间的一趟扫描算法吗？
 * //
 * // Related Topics 数组 双指针 排序 👍 1257 👎 0
 */

package com.xixi.basicAlgroithms.sort;

public class ID00075SortColors {
    public static void main(String[] args) {

        Solution solution = new ID00075SortColors().new Solution();
        solution.sortColors(new int[]{2,0,2,1,1,0});
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void sortColors(int[] nums) {

            //第一遍，先把0都放前面
            int front = 0;
            int tail = nums.length - 1;

            while (front < tail) {
                if (nums[front] == 0) { //front为0就继续往前找
                    front++;
                    continue;
                }
                if (nums[tail] != 0) {
                    tail--;
                    continue;
                }

                swap(nums, front, tail);
                front++;
                tail--;
            }

            //第二遍，先把1都放中间
            if(front < (nums.length - 1)){
                tail = nums.length -1 ;
                while (front < tail) {
                    if (nums[front] <= 1) {
                        front++;
                        continue;
                    }
                    if (nums[tail] == 2) {
                        tail--;
                        continue;
                    }

                    swap(nums, front, tail);
                    front++;
                    tail--;
                }

            }


        }



        public void swap(int[] nums, int a, int b) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}